/*
 * @Description:
 * @Author: chenjiaxin
 * @Date: 2022-06-12 09:04:37
 * @LastEditTime: 2022-06-12 15:03:08
 * @FilePath: \leetcode\3_链表\01_单向链表封装.js
 */
function LinkedList() {
  // 内部节点类
  function Node(data) {
    this.data = data;
    this.next = null;
  }

  // 属性
  this.head = null;
  this.length = 0;

  // 方法
  // 1. 追加方法
  LinkedList.prototype.append = function (data) {
    // 1. 创建新的节点
    const newNode = new Node(data);
    // 2. 判断是否第一个节点
    if (this.head == null) {
      // 2.1 是第一个节点
      this.head = newNode;
    } else {
      // 2.2 不是第一个节点

      // 2.2.1 找到最后一个节点
      let currentNode = this.head;
      while (currentNode.next) {
        currentNode = currentNode.next;
      }
      // 2.2.2 最后节点的next 指向新的节点
      currentNode.next = newNode;
    }
    // 3. 长度加一; += 适合很多编程语言 而 ++ 有的语言不支持 比如 python
    this.length += 1;
  };

  // 2. toString 方法
  LinkedList.prototype.toString = function () {
    let currentNode = this.head;
    let listString = "";
    // 循环获取才一个节点
    while (currentNode) {
      listString += currentNode.data + " ";
      currentNode = currentNode.next;
    }
    return listString;
  };

  // 3. insert 方法  插入
  /**
   *
   * @param {number} position : 插入的位子 0+;类似数组的索引。
   * 比如 A B C 他们的下标值分别为 0 1 2  当 insert(1, "Q") 把Q放在 下标1的位子 原来的往后移 =>  A Q B C
   * @param {*} data
   * 链表的
   */
  LinkedList.prototype.insert = function (position, data) {
    // 1. 边界判断(类型判断就不做了 推荐使用ts)
    if (position < 0 || position > this.length) {
      throw "position 错误";
    }
    // 2. 创建新节点
    let newNode = new Node(data);

    // 3. 判断position 是否0
    if (position == 0) {
      // 2.1 插入到 head 后面 最为一个节点
      // let originFirstNode = this.head;
      newNode.next = this.head; // this.head 就是原来的第一个节点
      this.head = newNode;
    } else {
      let index = 0;
      let currentNode = this.head;
      let previous = null;
      while (index++ < position) {
        // index += 1;
        previous = currentNode;
        currentNode = currentNode.next;
      }

      newNode.next = currentNode;
      previous.next = newNode;
    }
    // 4. 长度加一
    this.length += 1;
  };

  /**
   * 4. 通过 位置 获取数据
   * @param {number} position : ;
   */
  LinkedList.prototype.get = function (position) {
    // 1. 边界判断(类型判断就不做了 推荐使用ts)
    if (position < 0 || position >= this.length) {
      throw "position 错误";
    }
    let index = 0;
    let currentNode = this.head;
    while (index++ < position) {
      currentNode = currentNode.next;
    }
    return currentNode.data;
  };

  /**
   * 5. 返回该数据 在链表中的 下标值
   * @param {any} data
   */
  LinkedList.prototype.indexOf = function (data) {
    // 1. 定义下标值 和 当前节点
    let index = 0;
    let currentNode = this.head;
    // while (index < this.length) {
    //   if (currentNode.data === data) {
    //     break;
    //   }
    //   index += 1;
    //   currentNode = currentNode.next;
    // }
    // if (currentNode) {
    //   return index;
    // } else {
    //   return -1;
    // }

    // 2. 循环每个节点
    while (currentNode) {
      if (currentNode.data === data) {
        return index;
      }

      currentNode = currentNode.next;
      index += 1;
    }
    // 3. 说明currentNode 已经 是null 已经到最后 也没有找到 就返回 -1
    return -1;
  };

  /**
   * 6. 更新元素
   * @param {number} position : ;
   * @param {*} data
   */
  LinkedList.prototype.update = function (position, data) {
    // 1. 边界判断(类型判断就不做了 推荐使用ts)
    if (position < 0 || position >= this.length) {
      throw "position 错误";
    }

    let index = 0;
    let currentNode = this.head;
    while (index++ < position) {
      currentNode = currentNode.next;
    }

    currentNode.data = data;
  };

  /**
   * 7. 通过下标值删除 这个元素
   * @param {number} position : ;
   * return 删除的元素
   */
  LinkedList.prototype.removeAt = function (position) {
    // 1. 边界判断(类型判断就不做了 推荐使用ts)
    if (position < 0 || position >= this.length) {
      // throw "position 错误";
      return null;
    }

    let index = 0;
    let currentNode = this.head;
    let previous = null;
    if (position == 0) {
      // let currentNode = this.head;
      // this.head = currentNode.next;

      this.head = this.head.next;
    } else {
      while (index < position) {
        index += 1;
        previous = currentNode;
        currentNode = currentNode.next;
      }

      previous.next = currentNode.next;
    }

    this.length -= 1;
    return currentNode.data;
  };

  /**
   * 8. 删除链表中的这个元素
   * @param {any} data
   */
  LinkedList.prototype.remove = function (data) {
    let index = this.indexOf(data);
    return this.removeAt(index);
  };
}
